Encryption Algorithm.

용어 정리

평문Plaintext: 암호화가 이뤄지지 않은 메시지.
암호문Ciphertext: 암호화가 이뤄진 메시지.

고전적 암호 체계

원시적인 암호들은 사람이 직접 계산해야 하기 때문에, 현실적 한계로 인해 암호화와 복호화가 모두 단순하다.

Caesar Cipher

모든 알파벳에 동일한 수를 더하는 암호화 방법.
존내 간단하죠? 당연히 취약하다.

Affine Cipher

알파벳에 $k_{1}$ 을 곱하고, $k_{2}$ 를 더하는 암호화 방법.
만약 상대방이 암호화 방식에 대해 알고 있다면, $k_{1}$ 과 $k_{2}$ 를 최대 $26 \times 26$ 의 계산만으로도 쉽게 유추할 수 있으므로, 여전히 취약하다.

소인수 기반 암호 체계

매우 큰 수의 소인수분해가 아주 오래걸린다는 점에 기반한 암호 체계

(a) Euler Phi Function

자연수 $n$ 에 대해, $n$ 보다 작으면서 $n$ 과 서로소인 자연수의 개수를 $Φ (n)$ 으로 정의.

(b) Euler Phi Function의 주요성질

자연수 $m$ 과 $n$ 이 서로소일 경우, $Φ (m n) = Φ (m) Φ (n)$
임의의 소수 $p$ 에 대해, $Φ (p^{k}) = p^{k} - p^{k - 1}$

(c) Euler Theorem

자연수 $a$ 와 $n$ 이 서로소라면 $a^{Φ (n)}$ 을 $n$ 으로 나눈 나머지는 1이다.

a^{Φ (n)} \equiv 1 (mod n)

(a)의 정의로부터, 임의의 소수 $p$ 에 대해, $Φ (p) = p - 1$ 임이 자명하며, 그 역도 성립한다. 따라서 이는 소수만이 갖는 성질로서, 소수를 수학적으로 표현한 것이나 마찬가지이다.

소수를 수학적으로 표현할 수많은 방법 중 왜 하필 이거냐? 하면,
바로 (b)-2 와 같은 성질을 통해 소수를 활용할 수 있기 때문일 것이다.

물론 (b)-1이나, (c)의 성질 들을 볼 때, 서로소 또한 굉장히 중요하게 사용된다. #Q 솔직히 이 이상은 잘 모르겠다.

RSA Cryptosystem

그리고 1977년 암호체계에 혁명이 일어났다.

평문을 공개키 e로 암호화하며, 대응되는 개인키 d로 복호화할 수 있다.
여기서 중요한 것은 누구든지 암호화를 할 수 있다는 것이다. 하지만, 열람은 개인키를 가진 이만 할 수 있다는 비대칭 현상이다.

** encrypt
${(p l a i n t e x t)}^{e} \equiv (c i p h e r t e x t)$ (mod n)

** decrypt
${(c i p h e r t e x t)}^{d} \equiv (p l a i n t e x t)$ (mod n)

그렇다면, 위와같은 연산을 만족시킬 수 있는, e와 d는 어떻게 구하는가?

충분히 큰 소수 p, q를 선택하여, n = pq 를 정의한다.
$e \times d \equiv 1 (\mod Φ (n))$ 을 만족하는 e와 d를 결정한다. 결정된 두 값중 하나를 공개하면 다른 하나는 개인키가 되는 것이다.

p와 q는 키 쌍을 생성하기 위해 쓰인다.

먼저, n 또한 공개되는 값임을 알아야 한다.
당신이 암호화를 하기 위해 알아야 할 것은, e와 n이다.
다만 $Φ (n)$ 의 값은 알려져서는 안된다. 이것은 쌍을 이루는 두 키를 생성하는 핵심 정보이기 때문이다. 만약 $Φ (n)$ 을 안다면, e 값을 이용해 d를 쉽게 구할 수 있다.

'Euler Phi Function (b)-1' 에 의해 $Φ (n)$ = (p - 1)(q - 1) 이다.
따라서, p, q 값은 처음 키 쌍을 생성한 뒤로는 폐기하는 것이 보안상 안전하다.

이산로그 기반 암호 프로토콜

이산로그 문제의 난해함에 기반

원시근primitive root

x의 거듭제곱값을 m으로 나눈 나머지로 가능한 값이 1,2, ..., m-1일 때, x를 m의 원시근으로 정의
이는 $x \mod m, x^{2} \mod m, x^{3} \mod m, \dots, x^{m - 1} \mod m$ 가 모두 다른 값이라는 사실과 필요충분이다.